#include <GL/glut.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define TAILLE_POINT 10
#define TAILLE_LIGNE 5

/* Structure de point */
typedef struct _VertexList {

	int visible;
	int sommet;

	int x;
	int y;
	struct _VertexList *suiv;
} VertexList;

/* Début de la liste des vertex */
VertexList *dlist;
/* Fin de la liste des vertex */
VertexList *flist;

/* Vertex en cours d édition */
VertexList *edit=NULL;

/* Vertex apres lequel intervenir */
VertexList *pos=NULL;

/* numerotation en cours */
int iSommet;

/* Cherche un point dans la liste */
VertexList* rechercher( int x, int y, int d ){

	VertexList *r;

	for(r=dlist;r!=NULL;r=r->suiv){

		if( abs(r->x-x)<=d && abs(r->y-y)<=d ){
			return r;
		}

	}

	return NULL;

}

/* Ajoute un point en x y apre m */
void ajouterApres(int x, int y, VertexList *m){
	VertexList *v;
	VertexList *r;

	/* Si cest le premier ici */
	if( (r = rechercher(x,y,TAILLE_POINT)) == NULL ) {
		v = malloc(sizeof(VertexList));
		v->x=x;
		v->y=y;
		v->visible = 1;

		if(m==NULL){
			flist = v;
			dlist = v;
			v->suiv = NULL;
		} else if(m==flist){
			m->suiv = v;
			flist = v;
			v->suiv=NULL;
		} else {
			v->suiv = m->suiv;
			m->suiv = v;
		}
	/* S il est superposé a un autre */
	}else{

		v = malloc(sizeof(VertexList));
		v->x=r->x;
		v->y=r->y;
		v->visible = 0;

		if(m==NULL){
			flist = v;
			dlist = v;
			v->suiv = NULL;
		} else if(m==flist){
			m->suiv = v;
			flist = v;
			v->suiv=NULL;
		} else {
			v->suiv = m->suiv;
			m->suiv = v;
		}
	}
}

/* efface les points en x y */
void effacer(int x, int y){
	VertexList *e, *p;

	if(dlist==NULL)
		return;

	if(dlist->x==x && dlist->y == y){
		e = dlist;
		if(dlist == flist)
			flist = NULL;
		dlist = dlist->suiv;
		free(e);
	}

	e=dlist->suiv;
	p=dlist;

	while(e!=NULL) {
		if(e->x==x && e->y==y){

			p->suiv = e->suiv;

			if(flist==e)
				flist = p;

			free(e);
			e=p->suiv;
		}else{
			e=e->suiv;
			p=p->suiv;
		}
	}

}
		
/* Affichage du numero du sommet */
void Sommet( VertexList *v ){

	int i;
	char s[8];

	if(v->visible){
		sprintf(s,"%i",iSommet);

		glRasterPos2i(v->x+TAILLE_POINT,v->y+TAILLE_POINT);
		for(i=0;s[i]!='\0';i++)
			glutBitmapCharacter(GLUT_BITMAP_HELVETICA_18, s[i] );
	}

}

void affichage( void );
void redim( int large, int haut );
void souris( int button, int state, int x, int y );
void souris2(int x, int y);
void clavier(unsigned char key, int x , int y );
void freeALL();
void AfficherTexte();

int main( int argc, char **argv ){

	glutInit(&argc, argv);

	glutInitWindowSize(800,600);
	glutInitWindowPosition(200,100);
	glutInitDisplayMode(GLUT_RGBA|GLUT_DOUBLE);

	glutCreateWindow("Editeur de graphe");

	glutDisplayFunc(affichage);
	glutReshapeFunc(redim);
	glutMouseFunc(souris);
	glutPassiveMotionFunc(souris2);
	glutKeyboardFunc(clavier);
	glClearColor(1,1,1,0);
	glHint(GL_LINE_SMOOTH_HINT,GL_DONT_CARE);
	glPointSize(TAILLE_POINT);
	glLineWidth(TAILLE_LIGNE);
	glBlendFunc(GL_SRC_ALPHA,GL_ONE_MINUS_SRC_ALPHA);	

	atexit(AfficherTexte);

	glutMainLoop();

	return 0;
}


void affichage( void ){

	VertexList *e=dlist, *v;

	glClear(GL_COLOR_BUFFER_BIT);
	glEnable(GL_LINE_SMOOTH);
	glEnable(GL_BLEND);

	/* Lignes */
	glBegin(GL_LINE_STRIP);
	glColor3f(0,0,0);
	while(e!=NULL) {
		glVertex2i(e->x, e->y);
		e=e->suiv;
	}
	glEnd();

	/* Points */
	e = dlist;

	glBegin(GL_POINTS);
	glColor3f(0,0,0);

	while(e!=NULL) {
	
		if(e==flist) glColor3f(1,1,0);
		glVertex2i(e->x, e->y);
		if(e==flist) glColor3f(0,0,0);
		e=e->suiv;
	}
	glEnd();

	glColor3f(1,0,0);
	iSommet = 0;
	for( v=dlist; v!=NULL; v=v->suiv ){

		Sommet(v);
		if(v->visible) iSommet++;

	}

	glutSwapBuffers();
}

void redim( int large, int haut ){

	glViewport(0,0,large,haut);

	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	gluOrtho2D(0,large,0,haut);

	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();

	glutPostRedisplay();	
}

void souris( int button, int state, int x, int y ){

	VertexList *v;
				
	if(edit!=NULL&&state==GLUT_DOWN){
		edit=NULL;
		return;
	}


	switch(button) {

		case GLUT_LEFT_BUTTON:
			if(state==GLUT_DOWN){


				if(pos!=NULL){
					ajouterApres(x,600-y,pos);
					pos=NULL;
				}else
					ajouterApres(x,600-y,flist);


				glutPostRedisplay();
			}
			break;

		case GLUT_RIGHT_BUTTON:
			if(state==GLUT_DOWN) {
				if( (v=rechercher(x,600-y,TAILLE_POINT)) != NULL){
					effacer(v->x,v->y);
					glutPostRedisplay();
				}
			}
			break;

		case GLUT_MIDDLE_BUTTON:
			if(state==GLUT_DOWN){
				
				if( (v=rechercher(x,600-y,TAILLE_POINT)) != NULL){
					edit = v;
				}
			}
	}

}


void souris2(int x, int y){

	VertexList *r;
	int x0, y0;

	if(edit!=NULL){

		x0 = edit->x;
		y0 = edit->y;

		edit->x = x;
		edit->y = 600-y;

		while( (r=rechercher(x0,y0,0)) != NULL ){

			r->x = x;
			r->y = 600-y;
		}

		glutPostRedisplay();
	}

}

void clavier(unsigned char key, int x , int y ){

	switch(key){

		case 27:
			exit(0);
			break;

		case 'e':
			freeALL();
			glutPostRedisplay();

			break;

	}

}

void freeALL(){

	VertexList *v, *t;

	if(dlist==NULL) return;
	if(dlist->suiv==NULL){
		free(dlist);
		dlist = flist = NULL;
		return;
	}

	t = dlist;
	for( v=dlist->suiv; v!=NULL; v=v->suiv ){

		free(t);

		t=v;

	}

	free(t);
	dlist = flist = NULL;

}

void AfficherTexte(){

	int nb, i, j, **table, aretes;
	VertexList *v, **t, *p, *s;

	/* Affichage du nombre de sommets */ 
	nb=aretes=0;
	for(v=dlist;v!=NULL;v=v->suiv){
		if(v->visible) nb++;
		aretes++;
	}
	if(aretes>0) aretes = aretes-1;

	printf("%i %i\n",nb, aretes);

	/* Calcul des voisins */
	t = malloc(sizeof(VertexList*)*nb);
	table = malloc(sizeof(int*)*nb);
	
	for(i=0;i<nb;i++)
		table[i] = malloc(sizeof(int)*nb);

	for(i=0;i<nb;i++){

		for(j=0;j<nb;j++)

			table[i][j] = 0;

	}

	i=0;
	for(v=dlist;v!=NULL;v=v->suiv){
		if(v->visible){
			t[i++] = v;
			v->sommet=i;
		}else{

			for(j=0;j<i;j++){
				if(t[j]->x==v->x&&t[j]->y==v->y){
					v->sommet = t[j]->sommet;
					break;
				}
			}

		}
	}

	p=NULL;
	if(dlist!=NULL) s=dlist->suiv;
	for(v=dlist;v!=NULL;v=v->suiv){

		if(p!=NULL){
			table[p->sommet-1][v->sommet-1]=1;
			table[v->sommet-1][p->sommet-1]=1;
		}

		if(s!=NULL){
			table[s->sommet-1][v->sommet-1]=1;
			table[v->sommet-1][s->sommet-1]=1;
			s=s->suiv;
		}

		p=v;

	}

	/* Affichage des voisins */
	for(i=0;i<nb;i++){

		for(j=i+1;j<nb;j++)
			if(table[i][j])
				printf("%i %i\n", i,j);

	}
	printf("\n");

	free(t);
	free(table);
	freeALL();
}
